public class Test {
    /*
    题目 1：最佳买卖股票时机含冷冻期
     */
    public int maxProfit(int[] p) {
        int n = p.length;
        int[][] dp = new int[n][3];

        dp[0][0] = -p[0];
        // 0 的话就不用初始化了，老是记不住！
//        dp[0][1] = 0;
//        dp[0][2] = 0;

        for(int i = 1; i < n; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - p[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + p[i];
        }

        // 最后一天还是处于买入状态的话，那个买的钱是亏的！
        //return Math.max(dp[n - 1][0], Math.max(dp[n - 1][1], dp[n - 1][2]));

        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }

    /*
    题目 2: 买卖股票的最佳时机含手续费
     */
    public int maxProfit1(int[] p, int fee) {
        int n = p.length;

        int[] f = new int[n];
        int[] g = new int[n];

        f[0] = -p[0];

        for(int i = 1; i < n; i++){
            f[i] = Math.max(f[i - 1], g[i - 1] - p[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + p[i] - fee);
        }

        return g[n - 1];
    }

    /*
    题目 3：买卖股票的最佳时机Ⅲ
     */
    public int maxProfit2(int[] p) {
        int n = p.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];

        f[0][0] = -p[0];
        f[0][1] = f[0][2] = g[0][1] = g[0][2] -0x3f3f3f3f;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < 3; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - p[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + p[i]);
                }
            }


        }
        int ret = 0;
        for(int i = 0; i < 3; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }

        return ret;
    }

    /*
    题目 4：买卖股票的最佳时机Ⅳ
     */
    public int maxProfit(int k, int[] p) {
        int INF = 0x3f3f3f3f;
        int n = p.length;
        int[][] f = new int[n][k + 1];
        int[][] g = new int[n][k + 1];

        for(int i = 0; i < k + 1; i++){
            f[0][i] = g[0][i] = -INF;
        }
        f[0][0] = -p[0];
        g[0][0] = 0;


        for(int i = 1; i < n; i++){
            for(int j = 0; j < k + 1; j++){
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - p[i]);
                g[i][j] = g[i - 1][j];
                if(j - 1 >= 0){
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + p[i]);
                }
            }


        }
        int ret = 0;
        for(int i = 0; i < k + 1; i++){
            ret = Math.max(ret, g[n - 1][i]);
        }

        return ret;
    }

    /*
    动态规划：子数组系列 ~ ~
     */

    /*
    题目 5：最大子数组和
     */
    public int maxSubArray1(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n];
        int max = nums[0];
        dp[0] = nums[0];

        for(int i = 1; i < n; i++){
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
            if(max < dp[i]){
                max = dp[i];
            }
        }
        return max;
    }

    public int maxSubArray(int[] nums) {
        int n = nums.length;

        // 数组多申请一个空间，不需要在外面初始化！
        int[] dp = new int[n + 1];

        int ret = nums[0];


        for(int i = 1; i < n + 1; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i - 1], nums[i - 1]);
            ret = Math.max(ret, dp[i]);
        }

        return ret;
    }

    /*
    题目 6：环形子数组的最大和
     */
    public int maxSubarraySumCircular1(int[] nums) {
        int n = nums.length;

        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];

        int max = nums[0];
        int min = nums[0];

        int sum = 0;

        for(int i = 0; i < n; i++){
            sum += nums[i];
        }

        for(int i = 1; i < n + 1; i++){
            dp1[i] = Math.max(nums[i - 1], nums[i - 1] + dp1[i - 1]);
            dp2[i] = Math.min(nums[i - 1], nums[i - 1] + dp2[i - 1]);
            max = Math.max(max, dp1[i]);
            min = Math.min(min, dp2[i]);
        }

        return sum == min ? max :Math.max(max, sum - min);
    }

    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length;

        int[] f = new int[n + 1];
        int[] g = new int[n + 1];

        int sum = 0;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for(int i = 1; i < n + 1; i++){
            int x = nums[i - 1];
            f[i] = Math.max(x, x + f[i - 1]);
            max = Math.max(f[i], max);
            g[i] = Math.min(x, x + g[i - 1]);
            min = Math.min(g[i], min);
            sum += x;
        }

        return sum == min ? max : Math.max(max, sum - min);
    }


}
